#define _CRT_SECURE_NO_WARNINGS 1
/*
该题有多种解题思路，比如：
  1. 统计每个数字出现的次数，然后找出只出现1次的数字，缺点：需要借助辅助空间
  2. 对数据进行排序，然后找出只出现1次的数字，缺点：时间复杂度不是O(N)
而题目要求了，时间复杂度必须为O(N)线性时间复杂度，因此便增加了题目的难度。


题目说：只有一个数字出现一次，其余数字均出现3次，假设数组为{3,5,3,3}
通过分析可知：
3的二进制：0 0 0 0 0 0 1 1
5的二进制：0 0 0 0 0 1 0 1
3的二进制：0 0 0 0 0 0 1 1
3的二进制：0 0 0 0 0 0 1 1
		  0 0 0 0 0 1 3 4  二进制1的总数
对于出现3次的数字，各位出现的次数都是3的倍数，因此对统计的为1的比特总数%3
		  0 0 0 0 0 1 0 1 = 5
		  结果就是只出现一次的数字
*/


// 时间复杂度：O(32*N)--->O(N)  空间复杂度：O(1)
class Solution {
public:
	int singleNumber(vector<int>& nums) {
		int ans = 0;
		for (int i = 0; i < 32; ++i) {


			// 统计该每个数字第i个比特位为1的总数
			int total = 0;
			for (int num : nums) {
				total += ((num >> i) & 1);
			}


			// 如果total能够被3整除，说明只出现一次的数字在该位置上一定是0
			// 否则在该位置上一定是1
			if (total % 3) {
				ans |= (1 << i);
			}
		}
		return ans;
	}
};